package test3.recursion;

/**
 * 938. 二叉搜索树的范围和
 * 给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
 */
public class RangeSumBST {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(15);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(7);
        root.right.right = new TreeNode(18);
        int i = new RangeSumBST().rangeSumBST(root, 7, 15);
        System.out.println(i);

    }

    public int rangeSumBST(TreeNode root, int low, int high) {
        int sum = 0;
        if (root == null) {
            return sum;
        }
        if (root.left != null) {
            sum += rangeSumBST(root.left, low, high);
        }
        if (root.val >= low && root.val <= high) {
            sum += root.val;
        }
        if (root.right != null) {
            sum += rangeSumBST(root.right, low, high);
        }
        return sum;
    }

}

